/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2021年02月26日
*   描    述：
*   Copyright (C) 2021 All rights reserved.
*
* ================================================================*/


#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main(){
    int n = 0, m = 0;
    cin >> n >> m;

    map<int, vector<int>> main_iterm;
    map<int, vector<vector<int>>> annex;


    for(int i = 1; i <= m; i++){
        int x, y, z;
        cin >> x >> y >> z;
        if(z == 0){ //主件
            main_iterm[i] = {x, y};
        } else{
            if(annex.find(z) != annex.end()){
                annex[z].push_back({x, y});
            }else{
                annex[z] = {{x, y}};
            }
        }
    }

    vector<vector<int>> v;
    vector<vector<int>> w;

    v.push_back({});
    w.push_back({});

    m = main_iterm.size();
    vector<vector<int>>dp(m+1, vector<int>(n+1, 0));

    for(map<int, vector<int>>::iterator iter = main_iterm.begin(); iter != main_iterm.end(); iter++){
        vector<int> v_tmp;
        vector<int> w_tmp;

        v_tmp.push_back(iter->second[0]);
        w_tmp.push_back(iter->second[0] * iter->second[1]);

        if(annex.find(iter->first) != annex.end()){
            v_tmp.push_back(v_tmp[0] + annex[iter->first][0][0]);
            w_tmp.push_back(w_tmp[0] + annex[iter->first][0][0] * annex[iter->first][0][1]);

            if(annex[iter->first].size() > 1){
                v_tmp.push_back(v_tmp[0] + annex[iter->first][1][0]);
                w_tmp.push_back(w_tmp[0] + annex[iter->first][1][0]*annex[iter->first][1][1]);

                v_tmp.push_back(v_tmp[1] + annex[iter->first][1][0]);
                w_tmp.push_back(w_tmp[1] + annex[iter->first][1][0]*annex[iter->first][1][1]);
            }
            //cout << w_tmp[1]<<endl;
        }

        v.push_back(v_tmp);
        w.push_back(w_tmp);
    }

    for(int i = 1; i <= m; i++){
        for(int j = 10; j <= n; j += 10){
            int max_i = dp[i-1][j];

            int size = v[i].size();
            for(int k = 0; k < size; k++){
                if(j - v[i][k] >= 0)
                    max_i = max(max_i, dp[i-1][j-v[i][k]] + w[i][k]);
           }

           dp[i][j] = max_i;
        }
    }

    cout << dp[m][n];
}
